//Given N dices.Each dice has A faces.That means each dice has numbers from 1 to A.Given Sum S,
//	Find the number of ways to make the sum S if dices are rolled together.
#include <vector>
#include <iostream>
#include <string>
#include <sstream>

//recursion with memorization
int sum(int n, int s, int a) {
	std::vector<std::vector<int> > result(n);
	for (std::vector<std::vector<int> >::iterator i = result.begin(); i != result.end(); ++i) {
		i->resize(s);
		for (std::vector<int>::iterator j = i->begin(); j != i->end(); ++j) {
			*j = -1;
		}
	}
	int calc(int n, int s, int a, std::vector<std::vector<int> > &result);
	return calc(n,s,a,result);

}
int calc(int n, int s, int a, std::vector<std::vector<int> > &result) {
	if(s<n || s>n*a)
		return 0;
	if(n==1)
		return 1;
	if( result[n-1][s-1] != -1 ) //memorization
		return result[n-1][s-1];
	else {
		int sum = 0;
		for ( int i = 1; i<=a; ++i)
			sum += calc(n-1,s-i,a,result);
		result[n-1][s-1] = sum;
		return sum;
	}
}
//dynamic programming non-recursive
int calc_dynamic_programming(int n, int s, int a) {
	std::vector<std::vector<int> > result(n);
	for (std::vector<std::vector<int> >::iterator i = result.begin(); i != result.end(); ++i) {
		i->resize(s);
		for (std::vector<int>::iterator j = i->begin(); j != i->end(); ++j) {
			*j = 0;
		}
	}
	for (int j = 1; j <= a && j<= s; j++)
		result[0][j-1] = 1;
	for (int i = 2; i<=n; i++) {
		for (int j = 1; j<=s; j++) {
			for (int k = 1; k <= a && j-k>=1; k++) {
				result[i-1][j-1] += result[i-2][j-1-k];
			}
		}
	}
	return result[n-1][s-1];
}
void test_sum_of_dice(){
	while(true) { //to terminate, press ctrl+c
		std::cout << "enter N, S, and A[N S A]\n";
		std::string str;
		std::getline(std::cin,str);
		std::stringstream sstr(str);
		int n, s, a;
		sstr >>n; sstr>> s; sstr >> a;
		int num = sum(n,s,a);
		std::cout << "The number of ways is " << num << std::endl;
		int num2 = calc_dynamic_programming(n,s,a);
		std::cout << "The number of ways is " << num2 << std::endl;
	}
}